//
// Created by Luhang on 2023/5/26/026.
//

#ifndef INC_0513_HASHTABLE_H
#define INC_0513_HASHTABLE_H

#endif //INC_0513_HASHTABLE_H

#pragma once

#include <vector>
#include <iostream>
using namespace std;

namespace OpenAddress{
    enum State{
        EMPTY,
        EXIST,
        DELETE
    };

    template<class K, class V>
    struct HashData{
        pair<K, V> _kv;
        State _state = EMPTY;
    };

    template<class K, class V>
    class HashTableCopy{
    public:
        bool Insert(const pair<K, V>& kv){
            if (Find(kv.first))
                return false;

            //负载因子超过0.7就扩容
            if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7){
                size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
                HashTableCopy<K, V> newHT;
                newHT._tables.resize(newSize);

                //遍历旧表，重新映射到新表
                for (auto& data : _tables) {
                    if (data._state == EXIST)
                        newHT.Insert(data._kv);
                }

                _tables.swap(newHT._tables);
            }

            size_t hashI = kv.first % _tables.size();
            size_t i = 1;
            size_t index = hashI;
            while (_tables[index]._state == EXIST){
                index = hashI + i;
                index %= _tables.size();
                ++i;
            }
            _tables[index]._kv = kv;
            _tables[index]._state = EXIST;
            _n++;

            return true;
        }

        HashData<K, V>* Find(const K& key){
            if (_tables.size() == 0)
                return nullptr;

            size_t hashI = key % _tables.size();

            size_t i = 1;
            size_t index = hashI;
            while (_tables[index]._state != EMPTY){
                if (_tables[index]._state == EXIST && _tables[index]._kv.first == key)
                    return &_tables[index];

                index = hashI + i;
                index %= _tables.size();
                ++i;

                //如果找一圈还没找到，说明表中全为存在和删除
                if (index == hashI)
                    break;
            }
            return nullptr;
        }

        bool Erase(const K& key){
            HashData<K, V>* ret = Find(key);
            if (ret){
                ret->_state = DELETE;
                --_n;
                return true;
            } else
                return false;
        }

    private:
        vector<HashData<K, V>> _tables;
        size_t _n = 0;//储存的数据个数
    };

    void TestHashTable1(){
        int a[] = {3,33,2,13,1002,5,21};
        HashTableCopy<int, int> ht;
        for (auto e : a) {
            ht.Insert(make_pair(e,e));
        }
        if (ht.Find(13))
            cout << "13 exist" << endl;
        else
            cout << "13 not exist" << endl;
        ht.Erase(13);
        if (ht.Find(13))
            cout << "13 exist" << endl;
        else
            cout << "13 not exist" << endl;
    }
}

namespace HashBucketCopy{

    template<class K, class V>
    struct HashNode{
        HashNode<K, V>* _next;
        pair<K, V> _kv;

        HashNode(const pair<K, V>& kv)
        :_next(nullptr)
        ,_kv(kv)
        {}
    };

    template<class K>
    struct HashFunc{
        size_t operator()(const K& key){
            return key;
        }
    };

    template<>
    struct HashFunc<string>{
        size_t operator()(const string& s){
            size_t hash = 0;
            for (auto ch : s) {
                hash += ch;
                hash *= 31;
            }
            return hash;
        }
    };

    template<class K, class V, class Hash = HashFunc<K>>
    class HashTable{
        typedef HashNode<K, V> Node;
    private:
        vector<Node*> _tables;
        size_t _n = 0;
    public:

        ~HashTable(){
            for (auto& cur : _tables) {
                while (cur){
                    Node* next = cur->_next;
                    delete cur;
                    cur = next;
                }
                cur = nullptr;
            }
        }

        Node* Find(const K& key){
            if (_tables.size() == 0)
                return nullptr;
            Hash hash;
            size_t hashI = hash(key) % _tables.size();
            Node* cur = _tables[hashI];
            while (cur){
                if (cur->_kv.first == key)
                    return cur;
                cur = cur->_next;
            }
            return nullptr;
        }

        bool Erase(const K& key){
            Hash hash;
            size_t hashI = hash(key) % _tables.size();
            Node* cur = _tables[hashI];
            Node* prev = nullptr;
            while (cur){
                if (cur->_kv.first == key){
                    if (prev == nullptr)
                        _tables[hashI] = cur->_next;
                    else
                        prev->_next = cur->_next;
                    delete cur;
                    return true;
                } else{
                    prev = cur;
                    cur =  cur->_next;
                }
            }
            return false;
        }

        bool Insert(const pair<K, V>& kv){
            if (Find(kv.first))
                return false;

            Hash hash;

            if (_n == _tables.size()){
                size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
                vector<Node*> newTables(newSize, nullptr);
                for (auto& cur : _tables) {
                    while (cur){
                        Node* next = cur->_next;
                        size_t hashI = hash(cur->_kv.first) % newTables.size();

                        cur->_next = newTables[hashI];
                        newTables[hashI] = cur;
                        cur = next;
                    }
                }
                _tables.swap(newTables);
            }

            size_t hashI = hash(kv.first) % _tables.size();
            Node* newNode = new Node(kv);
            newNode->_next = _tables[hashI];
            _tables[hashI] = newNode;

            ++_n;
            return true;
        }
    };

    void TestHashTable1(){
        int a[] = {3,33,2,13,5,12,1002,6,9,21};
        HashTable<int, int> ht;
        for (auto e : a) {
            ht.Insert(make_pair(e,e));
        }
        ht.Insert(make_pair(22,22));
        ht.Erase(3);
        ht.Erase(1002);
        ht.Erase(6);
    }

    void TestHashTable2(){
        HashTable<string, string> ht;
        ht.Insert(make_pair("right","left"));
        ht.Insert(make_pair("increase","decrease"));
        ht.Insert(make_pair("in","out"));

        HashFunc<string> hashStr;
        cout << hashStr("eat") << endl;
        cout << hashStr("ate") << endl;
        cout << hashStr("increase") << endl;
        cout << hashStr("right") << endl;
    }
}